package offer;

import java.util.LinkedList;

public class offer_0059_1 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        LinkedList<int[]> queue=new LinkedList<>();
        int len=nums.length;
        if(len==0) return new int[0];
        int[] result=new int[len-k+1];
        int index=0;
        for(int i=0;i<k;++i){
            while(!queue.isEmpty()&&queue.getLast()[0]<nums[i]){
                queue.removeLast();
            }
            queue.add(new int[]{nums[i], i});
        }
        result[index]=queue.getFirst()[0];
        index++;
        for(int i=k;i<len;++i){
            if(i-k==queue.getFirst()[1]) queue.removeFirst();
            while(!queue.isEmpty()&&queue.getLast()[0]<nums[i]){
                queue.removeLast();
            }
            queue.add(new int[]{nums[i],i});
            result[index]=queue.getFirst()[0];
            index++;
        }
        return result;
    }
}
